1. Field of the Invention
The present invention relates to circuits that perform arithmetic operations. More specifically, the present invention relates to a method and an apparatus that uses the Newton-Raphson technique to perform a square-root operation within an arithmetic-logic unit (ALU) of a computer system.
2. Related Art
A number of techniques are presently used to perform divide and square-root operations in hardware. One popular technique is to use the Newton (sometimes called the Newton-Raphson) method.
According to the Mathematics Dictionary (edited by Glenn James and Robert C. James, D. Van Nostrand Company, Inc., Library of Congress Catalogue Card No. 59-8656 Copyright 1949, 1959), the Newton-Raphson method of approximation is a “step-by-step approximation to the roots of an equation in one unknown. It is based on the fact that the tangent of an ordinary curve very nearly coincides with a small arc of the curve, i.e., that the subtangent is approximately the same as the distance from the curve's x-intercept to the foot of the ordinate of the point whose abscissa is the last approximation to the root. Suppose the equation is ƒ(x)=0, and xi is an approximation to one of the roots. The next approximation, xi+1, is the abscissa of the point of intersection of the x-axis and the tangent to the curve y=ƒ(x) at the point whose abscissa is xi, i.e., xi+1=xi−ƒ(xi)/ƒ′(xi), where ƒ′(xi) is the derivative of ƒ(x) evaluated for x=xi. This is equivalent to using the first two terms (dropping all higher-degree terms) in Taylor's expansion of ƒ(x) about the point whose abscissa is xi and assuming that ƒ(xi+1)=0″ (variable names have been changed).
For a divide operation where a/b is to be determined, we first find 1/b and then multiply by a. To use the Newton-Raphson method, an equation is needed whose root is 1/b and for which the Newton-Raphson iterations can be computed using only multiplication, addition, and subtraction. Such an equation is:ƒ(x)=1−1/bx Note that x=1/b is a zero of this function, and its derivative is,ƒ′(x)=1/bx2 and so, the iterations use,
      x          i      +      1        =                    x        i            -                        1          -                      1                          bx              i                                                1                      bx            i            2                                =                            x          i                -                              (                          1              -                              1                                  bx                  i                                                      )                    ⁢                                          ⁢                      bx            i            2                              =                                    x            i                    -                      bx            i            2                    +                      x            i                          =                              x            i                    ⁢                                          ⁢                      (                          2              -                              bx                i                                      )                              
This may be computed in three steps:
1: multiply the previous estimate by the denominator;
2: subtract that result from two;
3: multiply the result of the subtraction by the previous estimate to produce a new better estimate.
These steps are repeated until sufficient accuracy is obtained, then the final estimate of 1/b is multiplied by the numerator a to produce a/b.
For square root, where the square root of a radicand b is to be determined, we first find 1/√{square root over (b)} and then multiply 1/√{square root over (b)} by b to obtain √{square root over (b)}. To use the Newton-Raphson method, an equation is needed whose root is 1/√{square root over (b)} and for which the Newton-Raphson iterations can be computed using only multiplication, addition and subtraction, and shifting. Such an equation is:ƒ(x)=1−1/bx2.Note that x=1/√{square root over (b)} is a zero of this function. Then, its derivative is ƒ(x)=2/bx3 and so, the iterations use,
      x          i      +      1        =    ⁢                    x        i            -                        1          -                      1                          bx              i              2                                                2                      bx            i            3                                =                            x          i                -                              (                          1              -                              1                                  bx                  i                  2                                                      )                    ⁢                                          ⁢                                    bx              i              3                        2                              =                                    x            i                    -                                    bx              i              3                        2                    +                                    x              i                        2                          =                                            (                                                2                  ⁢                                      x                    i                                                  -                                  bx                  i                  3                                +                                  x                  i                                            )                        2                    =                                                    x                i                            ⁡                              (                                                      3                    -                                          bx                      i                      2                                                        2                                )                                      .                              
This may be computed in five steps:
1: square the previous estimate;
2: multiply the square of the previous estimate by b;
3: subtract that result from three;
4: divide that by 2; and
5: multiply the result of the shift by the previous estimate, resulting in a new better estimate.
Note that if the representation of the result of step 3 above is an integer or fixed point, the divide by 2 in step 4 may be accomplished with a shift. However, if the representation is floating point, then the divide by two may be accomplished by subtracting one from the exponent. Also note that the description of the present invention that follows generally uses a fixed-point representation.
Steps 1-5 are repeated until sufficient accuracy is obtained, then the final estimate of 1/√{square root over (b)} is multiplied by b to obtain √{square root over (b)}.
Some systems provide a functional unit that can perform a multiply-add operation. In such systems, the divide operation can be completed more quickly by combining the first step (multiply) with the second step (subtract). Likewise, the square-root operation can be completed more quickly by combining the second step (multiply) with the third step (subtract).
Unfortunately, some systems do not provide hardware to support a multiply-add operation. In such systems, the Newton-Raphson method for performing a divide (or a square-root) operation requires an extra pass through an adder circuit to perform the subtraction operations. This increases the time required to perform the divide (or square-root) operation.